{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n队列：  添加新项的一端称为队尾，移除项的一端称为队首。\\n\\n先进先出\\n\\n可以用线性表或者链表实现\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "队列：  添加新项的一端称为队尾，移除项的一端称为队首。\n",
    "\n",
    "先进先出\n",
    "\n",
    "可以用线性表或者链表实现\n",
    "\n",
    "回文检查问题。\n",
    "队列可以帮助构建定时仿真。\n",
    "模拟使用随机数生成器来创建真实情况，并帮助我们回答“假设”类型的问题。\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0\n",
      "False\n",
      "1\n",
      "a\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class Queue(object):\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0,item)\n",
    "    \n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    q = Queue()\n",
    "    print(q.isEmpty())\n",
    "    print(q.size())\n",
    "    q.enqueue(1)\n",
    "    q.enqueue('a')\n",
    "    q.enqueue('dog')\n",
    "    print(q.isEmpty())\n",
    "    q.enqueue(8.4)\n",
    "    print(q.dequeue())\n",
    "    print(q.dequeue())\n",
    "    print(q.size())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Susan\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Josephu问题\n",
    "    他们围成一个圈，其中一人被指定为第一个人，顺时针报数到第七人，就将他杀死。\n",
    "    约瑟夫斯是一个成功的数学家，他立即想出了应该坐到哪才能成为最后一人。\n",
    "\"\"\"\n",
    "def JosephuQuestion(name_list, num):\n",
    "    \"\"\"\n",
    "        num_list 表示所有人\n",
    "        num 表示计数，第3个，第7个\n",
    "    \"\"\"\n",
    "    q = Queue()\n",
    "    for i in name_list:\n",
    "        q.enqueue(i)\n",
    "\n",
    "    while q.size() > 1:\n",
    "        for i in range(num):\n",
    "            q.enqueue(q.dequeue())\n",
    "        q.dequeue()\n",
    "    return q.dequeue()\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(JosephuQuestion([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"],7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average Cost  55.68 secs   2 tasks remaining.\n",
      "Average Cost 330.10 secs   1 tasks remaining.\n",
      "Average Cost  13.60 secs   0 tasks remaining.\n",
      "Average Cost 148.86 secs   1 tasks remaining.\n",
      "Average Cost  19.53 secs   1 tasks remaining.\n",
      "Average Cost  83.72 secs   0 tasks remaining.\n",
      "Average Cost  44.09 secs   0 tasks remaining.\n",
      "Average Cost 101.56 secs   7 tasks remaining.\n",
      "Average Cost  75.62 secs   2 tasks remaining.\n",
      "Average Cost  42.80 secs   0 tasks remaining.\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "共线打印机问题\n",
    "\"\"\"\n",
    "import random\n",
    "\n",
    "class Task(object):\n",
    "    \"\"\" 任务调度类 \"\"\"\n",
    "    def __init__(self, time):\n",
    "        self.time_start = time\n",
    "        self.pages = random.randint(1,20)  # 随机生成1-20张，包括下限1和上限20\n",
    "        \n",
    "    def get_stime(self):\n",
    "        return self.time_start\n",
    "    \n",
    "    def get_pages(self):\n",
    "        return self.pages\n",
    "    \n",
    "    # 从打印队列到被执行的时间\n",
    "    def wait_time(self, current_time):\n",
    "        return current_time - self.time_start\n",
    "\n",
    "\n",
    "class Printer(object):\n",
    "    \"\"\" 打印机 \"\"\"\n",
    "    def __init__(self, ppr):\n",
    "        # 打印速度 每分钟几张\n",
    "        self.paper_rate = ppr\n",
    "        self.current_tast = None\n",
    "        # 理论上该打印任务的剩余，执行时间，\n",
    "        # 根据打印机的速度和任务的paper数能推断出来\n",
    "        self.time_remaining = 0\n",
    "        \n",
    "    # 滴答计时函数\n",
    "    def tick(self):\n",
    "        if self.current_tast is not None:\n",
    "            self.time_remaining -= 1\n",
    "            if self.time_remaining == 0:\n",
    "                # 任务到时间了，移除任务\n",
    "                self.current_tast = None\n",
    "    \n",
    "    # 打印机是否繁忙，是否有打印任务\n",
    "    def busy(self):\n",
    "        if self.current_tast is not None:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    # 开始执行打印任务\n",
    "    def start_next(self,task):\n",
    "        self.current_tast = task\n",
    "        # 打印任务的执行时间 多少秒\n",
    "        self.time_remaining = task.get_pages()*60/self.paper_rate\n",
    "\n",
    "def simulation_printer(sec, rates):\n",
    "    \"\"\" sec: 模拟运行时间; rates: 打印机的运行速度 \"\"\"\n",
    "    printer = Printer(rates)\n",
    "    q = Queue()\n",
    "    # 保留每个任务的等待时间\n",
    "    wait_times = []\n",
    "    \n",
    "    for i in range(sec):\n",
    "        if random.randint(1,180) is 180:\n",
    "            \"\"\" 产生随机任务 \"\"\"\n",
    "            task = Task(i)\n",
    "            q.enqueue(task)\n",
    "        \n",
    "        if not printer.busy() and not q.isEmpty():\n",
    "            task = q.dequeue()\n",
    "            wait_times.append(task.wait_time(i))\n",
    "            printer.start_next(task)\n",
    "\n",
    "        printer.tick()\n",
    "    \n",
    "    average_cost=sum(wait_times)/len(wait_times)\n",
    "    print(\"Average Cost %6.2f secs %3d tasks remaining.\"%(average_cost, q.size()))\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    for i in range(10):\n",
    "#         print(random.randrange(1, 181))\n",
    "        simulation_printer(3600, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
